#include"stack_queue.h"
#include<iostream>
using namespace std;


MyStack::MyStack()
{
    base = new Node;
    top = base;
    l = 0;
};
bool MyStack::push(const int& a)
{
    if (l < 20)
    {
        Node* p = new Node;
        p->data = a;
        p->next = top;
        top = p;
        l++;
        return true;
    }
    return false;
};
void MyStack::printStack()
{
    if (l)
    {
        Node* p = top;
        cout << p->data;
        p = p->next;
        while (p != base)
        {
            cout << "," << p->data;
            p = p->next;
        }
    }
    cout << endl;
}; //1
bool MyStack::pop(int& item)
{
    if (l)
    {
        item = top->data;
        Node* p = top;
        top = top->next;
        l--;
        delete p;
        return true;
    }
    return false;
};
bool MyStack::getTop(int& item)
{
    if (l)
    {
        item = top->data;
        return true;
    }
    return false;
};
MyQueue::MyQueue(const int& n)
{
    p = new int[n];
    tail = p;
    top = p;
    l = 0;
    Capacity = n;
}
//MyQueue::~MyQueue()
bool MyQueue::enQueue(const int& a)
{
    if (l < Capacity)
    {
        *tail = a;
        tail++;
        l++;
        return true;
    }
    return false;
}
bool MyQueue::deQueue(int& item)
{

    item = *top;
    top++;
    l--;
    return true;
}
void MyQueue::recycleQue()
{
    tail = top;
}
bool MyQueue::getFront(int& item)
{
    item = *top;
    return true;
}
void MyQueue::printQueue()
{
    int* q = top;
    cout << *q;
    q++;
    while (q < tail)
    {
        cout << "," << *q;
        q++;
    }
    cout << endl;
}
void MyQueue::printQueue00()
{
    int* q = top + 1;
    if (*q)
        cout << *q;
    q++;
    while (q < tail)
    {
        if (*q)
            cout << "," << *q;
        q++;
    }
    cout << endl;
}

int ComPriority(char a, char b)
{
    if (a == '-' || a == '+')
    {
        if (b == '/' || b == '*')
            return 0;
    }
    else
        return 1;
}

void postfixExpression(const string& a, string& result)
{
    int cnt = 0;
    string acp = a;
    for (int i = 0; i < acp.length(); i++)
    {
        if (acp[i] == '(')
        {
            for (int j = i; j < acp.length(); j++)
            {
                if (acp[j] == ')')
                {
                    cnt += 2;
                    acp[i] = '@';
                    acp[j] = '@';
                    break;
                }
            }
        }
    }
    for (int i = 0; i < acp.length(); i++)
        if (acp[i] == '(' || acp[i] == ')')
        {
            result = "Expression is wrong!";
            return;
        }
   
    char* b = new char[a.length()];
    MyStack s;
    int j = 0;
    int rub = 0;
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] >= '0' && a[i] <= '9')
        {
            b[j++] = a[i];
            while (a[i + 1] >= '0' && a[i + 1] <= '9')
                b[j++] = a[++i];
        }
        else if (a[i] == '(')
            s.push(a[i]);
        else if (a[i] == ')')
        {
            while (s.top->data != '(')
            {
                b[j++] = (char)s.top->data;
                s.pop(rub);
            }
            s.pop(rub);
        }
        else
        {
            while (s.l && s.top->data != '(' && ComPriority(a[i], s.top->data))
            {
                b[j++] = (char)s.top->data;
                s.pop(rub);
            }
            s.push(a[i]);
        }
    }
    while (s.l)
    {
        if (s.top->data > 39 && s.top->data <= '9')
        {
            b[j++] = s.top->data;
            s.pop(rub);
        }
        else s.pop(rub);
    }
    char* c = new char[a.length() - cnt];
    for (int i = 0;i < a.length() - cnt;i++)
    {
        c[i] = b[i];
    }
    result = c;
}

bool expressionVal(const string& a, int& result)
{
    char* b = new char[a.length()];
    MyStack s;
    MyStack n;
    int j = 0;
    int rub = 0;
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] >= '0' && a[i] <= '9')
        {
            n.push(a[i] - '0');
            while (a[i + 1] >= '0' && a[i + 1] <= '9')
                n.push(a[++i] - '0');
        }
        else if (a[i] == '(')
            s.push(a[i]);
        else if (a[i] == ')')
        {
            while (s.top->data != '(')
            {
                int cnt1, cnt2;
                s.pop(rub);
                switch ((char)rub)
                {
                case '+':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt1 + cnt2);
                    break;
                }
                case '-':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt2 - cnt1);
                    break;
                }
                case '/':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt2 / cnt1);
                    break;
                }
                case '*':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt2 * cnt1);
                    break;
                }
                }
            }
            s.pop(rub);
            int cnt1, cnt2;
            switch ((char)rub)
            {
            case '+':
            {
                n.pop(cnt1);
                n.pop(cnt2);
                n.push(cnt1 + cnt2);
                break;
            }
            case '-':
            {
                n.pop(cnt1);
                n.pop(cnt2);
                n.push(cnt2 - cnt1);
                break;
            }
            case '/':
            {
                n.pop(cnt1);
                n.pop(cnt2);
                n.push(cnt2 / cnt1);
                break;
            }
            case '*':
            {
                n.pop(cnt1);
                n.pop(cnt2);
                n.push(cnt2 * cnt1);
                break;
            }
            }
        }
        else
        {
            while (s.l && s.top->data != '(' && ComPriority(a[i], s.top->data))
            {
                b[j++] = (char)s.top->data;
                s.pop(rub);
                int cnt1, cnt2;
                switch ((char)rub)
                {
                case '+':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt1 + cnt2);
                    break;
                }
                case '-':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt2 - cnt1);
                    break;
                }
                case '/':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt2 / cnt1);
                    break;
                }
                case '*':
                {
                    n.pop(cnt1);
                    n.pop(cnt2);
                    n.push(cnt2 * cnt1);
                    break;
                }
                }
            }
            s.push(a[i]);
        }
    }
    while (s.l)
    {
        s.pop(rub);
        int cnt1, cnt2;
        switch ((char)rub)
        {
        case '+':
        {
            n.pop(cnt1);
            n.pop(cnt2);
            n.push(cnt1 + cnt2);
            break;
        }
        case '-':
        {
            n.pop(cnt1);
            n.pop(cnt2);
            n.push(cnt2 - cnt1);
            break;
        }
        case '/':
        {
            n.pop(cnt1);
            n.pop(cnt2);
            n.push(cnt2 / cnt1);
            break;
        }
        case '*':
        {
            n.pop(cnt1);
            n.pop(cnt2);
            n.push(cnt2 * cnt1);
            break;
        }
        }
    }
    n.pop(result);
    return true;
}
void yanghui(const int& a)
{
    MyQueue q1(30);
    MyQueue q2(30);
    if (a >= 1)
    {
        q1.enQueue(0);
        q1.enQueue(1);
        q1.enQueue(0);
        int cnt = a;
        while (cnt--)
        {
            int crt1, crt2;
            while (q1.l > 1) 
            {
                q1.deQueue(crt1);
                q1.getFront(crt2);
                q2.enQueue(crt1 + crt2);
                
            }
            while (q2.l)
            {
                q2.deQueue(crt1);
                q1.enQueue(crt1);
            }
            q1.enQueue(0);
            q1.printQueue00();
        }
    }
}
